package com.yihusitian.leecode.algorithm.easy;

import java.util.Objects;

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 * 1 <= strs.length <= 200
 * 0 <= strs[i].length <= 200
 * strs[i] 仅由小写英文字母组成
 *
 */
public class LongestCommonPrefix {

    public String longestCommonPrefix1(String[] strs) {
        if (Objects.isNull(strs) || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        if (strs.length == 2) {
            return this.getSamePrefix(strs[0], strs[1]);
        }

        String minlengthstr = strs[0];
        int minlength = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < minlength) {
                minlength = strs[i].length();
                minlengthstr = strs[i];
            }
        }

        String sameprefix = this.getSamePrefix(minlengthstr, strs[0]);
        for (int i = 1; i < strs.length; i++) {
            sameprefix = this.getSamePrefix(sameprefix, strs[i]);
            if (sameprefix.length() == 0) {
                return sameprefix;
            }
        }

        return sameprefix;
    }

    public String longestCommonPrefix(String[] strs) {
        if (Objects.isNull(strs) || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String sameprefix = this.getSamePrefix(strs[0], strs[1]);
        if (strs.length == 2 || sameprefix.length() == 0) {
            return sameprefix;
        }
        for (int i = 2; i < strs.length; i++) {
            sameprefix = this.getSamePrefix(sameprefix, strs[i]);
            if (sameprefix.length() == 0) {
                return sameprefix;
            }
        }
        return sameprefix;
    }

    private String getSamePrefix(String a, String b) {
        StringBuilder stringBuilder = new StringBuilder();
        String minstr = a.length() < b.length() ? a : b;
        for (int i = 0; i < minstr.length(); i++) {
            char achar = a.charAt(i);
            char bchar = b.charAt(i);
            if (achar == bchar) {
                stringBuilder.append(achar);
            } else {
                break;
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new LongestCommonPrefix().longestCommonPrefix1(new String[]{"aaac", "aaa", "aabb"}));
    }
}
